Distributed data-storage systems (“DSSs”) are complicated software solutions that operate over hardware infrastructures consisting of a large number of servers of various designations that are connected together by multiple communication channels. Existing DSSs are subject to various kinds of hardware failures, including total or partial switching off of the electrical supply, network failures that may result in the DSS being divided into separate unconnected segments, disk failures, and the like.
Conventionally, there are two main approaches to ensuring reliability of data storage in conditions of failure, based on the duplication of information and the spreading of data over different components of the distributed data-storage system. The first approach is data replication and the second approach is erasure coding.
In general, data replication is the storage of each block of data (i.e., file or object, depending on the architecture of the data-storage system) in several copies on different disks or different nodes of the system. As a result, replication makes it possible to ensure maximum efficiency of data access, including a significant increase in speed of read access to data frequently used by different clients. However, data replication can be very costly from the perspective of the amount of disk space needed to create the several copies of each block of data.
Moreover, noiseless (or lossless) coding is based on the use of mathematical algorithms that make it possible, to generate n chunks (i.e., data fragments or “derivatives”) of a block of data using compression techniques in such a way that any k chunks will be sufficient to recover the initial block of data. Each of the n chunks obtained should be written to a separate disk, and, preferably, to a separate server to ensure high availability of the data. The reliability of a scheme of noiseless coding with parameters n,k (i.e., an “(n,k) scheme”) is comparable to the reliability with replication of data with n−k+1 copies of each data block.
The use of noiseless coding makes it possible to reduce considerably the overheads on data storage necessary for data replication—the redundancy of data storage (i.e., including the ratio of the volume of storable data to the volume of useful data) for an (n,k) scheme is equal to n/k (the size of a data chunk is approximately equal to SizeBlock/k, where SizeBlock is the volume of the initial block of data). The most widely used error-correcting codes in modern software systems of data storage are Reed-Solomon codes and variations, such as Cauchy codes, for example.
In these fault tolerant storage systems, usually any data fragment is split into k+m chunks, where k are the data chunks and m is number of chunks generated on the basis of data chunks. For the generation, the error-correcting codes, such as the Reed-Solomon codes, allow the system to avoid primitive data duplication, but provide a very reliable mechanism that helps to restore all data even if some disks or servers become damaged. For example, to restore any k data chunks, the system should store k+m chunks. If any m chunks are lost, the system can completely restore all the data with remaining k chunks and it does not matter if they are data chunks or generated chunks.
Moreover, the schemes can be different. For example, the system can store k unchanged data chunks and m calculated chunks. Alternatively, the system can store mixed n chunks (as described above), which are combined from k and m chunks in different ways. When archiving the data, the system can save n=k+m chunks on N servers (or disks). Data is to are considered to be saved if all the N servers confirmed the each of N chunks was successfully recorded to storage.
Under the (n,k) scheme, each derivative is unique meaning that there are no duplicates of derivatives. Moreover, it assumed that every existing or potentially possible derivative has a unique number in the range from one to max. In principle, it is possible that this is all built over the Galois field GF (2n), then the maximum number of derivatives limited by possibilities of their numbering in the field.
In certain circumstances, the system may need to create a new derivative with the number i, on one of the servers s, which can be a server currently storing a derivative or a new server. Conventionally, systems create the new derivative i by having the client (who owns the stored data) connect to the system and collect k derivatives. Next, the client will then collect the original file, decrypt it and then generate a derivative i. Finally, the client must then connect to server s and store the derivative i to the server s.
However, there are certain technical disadvantages with this methodology for creating a new derivative i. For example, the client must be online since only the client knows the encryption keys, including keys to the directory, which may be required for storage of data on the servers. Moreover, there may be large overhead since it is necessary to download the entire file, then spend CPU resource on its assembly and the generation of a new derivative, and then upload it to the server. In other words, the client device has too expend significant computing resources.
One possible solution is the separation of the classical encryption and the (n,k) scheme. That is, implementation of the operation of the assembly and disassembly of the file using (n,k) is performed after the usual file encryption. As a result, the client device does not have to be online in this case, but the system still requires a single server that is going to be doing all the work described above with respect to the individual client, and have the same overhead costs, with potentially serious network load.
Accordingly, there is a need for a system and method to restore data integrity for data storage using (n,k) schemes that optimizes assembly time and network load.